package com.lw.leetcode.arr.b;

import java.util.ArrayList;
import java.util.List;

/**
 * 442. 数组中重复的数据
 *
 * @Author liw
 * @Date 2021/5/23 10:36
 * @Version 1.0
 */
public class FindDuplicates {


    public static void main(String[] args) {
        FindDuplicates test = new FindDuplicates();
//        int[] arr = {10,2,5,10,9,1,1,4,3,7};
        int[] arr = {4, 3, 2, 7, 8, 2, 3, 1};
        List<Integer> list = test.findDuplicates(arr);
        System.out.println(list);
    }

    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            if (num < 0) {
                num = ~num + 1;
            }
            num--;
            int value = nums[num];
            if (value < 0) {

                list.add(num + 1);
            } else {
                nums[num] = ~value + 1;
            }
        }
        return list;
    }
}
